class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        int hash1[26] = {0}; // 统计p字符串的字符出现个数
        int hash2[26] = {0}; // 统计s字符串的字符出现个数
        vector<int> ret;
        int psize = p.size();
        int count = 0; // 统计s串有效字符
        //统计p串的字符出现个数
        for(auto e : p)
        {
            hash1[e - 'a']++;
        } 

        for(int left = 0, right = 0; right < s.size(); right++)
        {
            char in = s[right];
            //进窗口
            hash2[in - 'a']++;
            //维护conut
            if(hash2[in - 'a'] <= hash1[in - 'a'])
                count++;
            //判断
            if(right - left + 1 > psize)
            {
                //出窗口 + 维护count
                char out = s[left];
                left++;
                if(hash2[out-'a'] <= hash1[out-'a']) 
                    count--;
                hash2[out - 'a']--;
            }
            //更新结果
            if(count == psize)
                ret.push_back(left);
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ret; //保存结果
        unordered_map<string,int> hash1; //统计words中单词出现的次数
        //统计words中单词出现的频次
        for(auto& s : words)
            hash1[s]++;
        int len = words[0].size(), sz = words.size();
        for(int i = 0; i < len; i++)
        {
            unordered_map<string,int> hash2; // 统计窗口中单词出现的个数
            for(int left = i, right = i, count = 0;right < s.size();right += len)
            {
                //进窗口 + 维护count
                string in = s.substr(right, len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) 
                    count++;
                if(right - left + 1 > len * sz)//判断
                {
                    //出窗口
                    string out = s.substr(left,len);
                    if(hash1.count(out) && hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;
                    left += len;
                }
                //更新结果
                if(sz == count)
                    ret.push_back(left);
            }
        }
        return ret;
    }
    
};